package 滑动窗口;

import java.util.HashMap;
import java.util.Map;

public class No76最小覆盖子串 {

    /**
     * 给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，
     * 从字符串 S 里面找出：包含 T 所有字符的最小子串。
     * 示例：
     * 输入：S = "ADOBECODEBANC", T = "ABC"
     * 输出："BANC"
     * 提示：
     * 如果 S 中不存这样的子串，则返回空字符串 ""。
     * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
     */

    public static String minWindow(String s, String t) {

        //左右移动后检验是否包含完毕,然后取最小值
        Map<Character,Integer> window=new HashMap<>();
        Map<Character,Integer> need=new HashMap<>();
        int valid=0;
        int left=0;
        int right=0;
        int min=-1;
        int[] result=new int[2];

        for(int i=0;i<t.length();i++){
            need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);
        }

        while(right<s.length()){

            if(right<s.length()){
                char c=s.charAt(right);
                if(need.containsKey(c)){
                    window.put(c,window.getOrDefault(c,0)+1);
                    if(window.get(c).equals(need.get(c)))
                        valid++;
                }
            }
            right++;

            /**
             * 1.右指针移动时如何维护
             * 更新widowMap和是否自增valid
             * 2.左指针什么时候移动
             * 题目是在最小覆盖子串,所以是valid符合need.size时就移动
             * 3.左指针移动时怎么维护
             * 吐出window,然后检验valid是否符合
             * 4.什么时候更新结果?
             * 在小while每次左指针移动的时候,符合就更新一下min,然后根据min更新result。
             */
            //这里应该是while,因为要根据那四个问题来说,更新结果应该是在valid==need.size里
            //先走了

            while (valid==need.size()){
                //符合条件了
                int ret=right-left;
                min=min==-1?ret:Math.min(min,ret);
                if(ret==min) {//min已经更新
                    result[0]=left;
                    result[1]=right;
                }
                //然后开始吐出windowMap,并且检查valid是否需要更新
                if(need.containsKey(s.charAt(left))){
                    //value减1
                    window.put(s.charAt(left),window.get(s.charAt(left))-1);

                    //windowMap存在目标字符,并且小于了
                    if(window.get(s.charAt(left))<(need.get(s.charAt(left))))
                        valid--;
                }
                left++;
            }
        }

        return s.substring(result[0], result[1]);
    }

    public static void main(String[] args) {
        String s = minWindow("ADOBECODEBANC", "ABC");
        System.out.println(s);
    }

}
